class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[8];
    void dfs(vector<int>& nums)
    {
        if(path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }// 当遇到答案之后
        // 没有遇到答案
        for(int i = 0;i<nums.size();i++)
        {
           // 下面是第二种剪枝操作我们只进入合法的分支
           if(check[i] == false&& (i == 0||nums[i-1] != nums[i]||check[i-1] == true))
           {
               //当i这个元素没有在上层使用过，并且是i等于0，或者是i不等于0但是i和前面的那个元素不一样
               // 或者是前面的那个元素和当前的这个元素不在同一层
               //这就代表当前的i这个元素是可以进入到path中的
               path.push_back(nums[i]);
               check[i] = true;
               dfs(nums);
               // 进行回溯恢复现场
               check[i] = false;
               path.pop_back();
           }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums);
        return ret;
    }
};